“Media-on-demand” (“MOD”) is a term often used to refer to a client-server system, where many clients make requests from a choice of many possible media objects that are to be served by a server (or array of servers) to the clients. In general, a design goal of a MOD system is to allow a client to request a media object or stream and have the content play at the client with no interruptions. The on-demand implies that there is little to no delay experienced by the client before the media object starts playing out at the client. On-demand also implies that the media object starts playing out from the beginning or possibly some specified point in the content, as opposed to joining a transmission in progress. One example is a video-on-demand system, where large numbers of clients may each make requests among many different digital videos.
A digital cable broadcasting system is a digital video server, as it serves up many digital video streams to many clients (end-user televisions, for example). Such a system might support hundreds of independent video streams and millions of clients. The system can be easily built, however customers are constrained to receive only the pre-selected set of videos at the times selected by the system operator, so the system is not on-demand.
A true media-on-demand system is much more difficult to build because the system may have to serve as many different streams as there are active clients, as each client demands different content (media objects) or the same content at different times. Potentially each client will require an independent stream of the media object it requested, where a stream is the flow of data required by that client in order to play out the content from the beginning without interruptions.
Some work relating to MOD systems proposes using broadcast or multicast mechanisms in order for the MOD system to be scalable to a large number of clients. See for example, J. W. Wong, “Broadcast delivery”, Proceedings of the IEEE, 76(12):1566–1577, (December 1988).
The different multicast or broadcast strategies that have been proposed in the literature can be divided into two distinct classes: (1) user-centered and (2) data-centered. See, e.g., S. Viswanathan and T. Imielinski, “Metropolitan area video-on-demand services using pyramid broadcasting”, Multimedia Systems, 4(4):197–208 (August 1996) (hereinafter “Viswanathan”). In user-centered strategies, the server bandwidth is allocated according to client requests, i.e., the bandwidth assigned at the server to serve a particular media object can vary over time depending on how many clients are requesting that media object. In data-centered strategies, the server bandwidth is allocated among the different media objects, i.e., the bandwidth assigned at the server to serve a particular media object is constant over time.
A typical user-centered strategy is “batching”, wherein all clients that make a request during an interval for the same media object are all serviced by one stream. There are a number of batching schemes that consider the various possible scheduling policies for assigning the available server bandwidth to a particular media object. See, e.g., C. Aggarwal, J. Wolf, and P. Yu, “On optimal batching policies for video-on-demand storage servers”, Proc. Intl. Conf on Multimedia Computing and Systems, pp. 253–258, Hiroshima, Japan, (June 1996) (hereinafter “Aggarwal”); K. C. Almeroth and M. H. Ammar, “The use of multicast delivery to provide a scalable and interactive video-on-demand service”, IEEE Journal on Selected Areas in Communication, 14(6):1110–1122, (August 1996); A. Dan, D. Sitaram, and P. Shahabuddin, “Scheduling policies for an on-demand video server with batching”, Proc. ACM Multimedia, pp. 391–398 (October 1998).
Another user-centered approach is stream merging, where a client receives data from multiple streams simultaneously, and the extra streams are dropped once the client catches up to the next existing stream. See, e.g., A. Bar-Noy and R. E. Ladner, “Competitive on-line stream merging algorithms for media-on-demand”, Draft (July 2000); A. Bar-Noy and R. E. Ladner, “Efficient algorithms for optimal stream merging for media-on-demand”, Draft (August 2000); D. Eager, M. Vernon, and J. Zahorjan, “Minimizing bandwidth requirements for on-demand data delivery”, Proc. Intl. Workshop on Advances in Multimedia Information Systems, pages 80–87, (Indian Wells, Calif., October 1999) (hereinafter “EagerMIS99”); and D. Eager, M. Vernon, and J. Zahorjan, “Optimal and efficient merging schedules for video-on-demand servers”, Proc. ACM Multimedia, vol. 7, pages 199–203 (1999). For user-centered strategies, the server bandwidth requirement for a particular media object can be expected to grow with the frequency of user requests for that media object. This may be acceptable for a small number of users, but may be infeasible if the number of users grows very large for very popular content.
Data-centered strategies are scalable to potentially millions of users as, unlike user-centered strategies, the server bandwidth required to serve a single media object is independent of the number of user requests or the frequency of user requests. A simple data-centered strategy is to divide the available bandwidth for a media object equally among C channels, and to retransmit the media object over one of the channels at equally spaced time intervals. For example, some pay-per-view digital satellite systems show the same one and half to two hour movie on four different channels, where a new transmission starts every half an hour. In this case, the worst case startup latency is just less than half an hour, where the startup latency, Ts, is defined to be the amount of time that passes between when the client requests the media object and the media object commences playing out on the client's media object player. The startup latency, Ts, may include delays such as processing the client's request at the server, propagation delay in the network, and decoding and encoding delays at the client and server respectively. Halving the startup latency for a media object requires doubling the number of channels and therefore the server bandwidth requirement also doubles.
Viswanathan describes “pyramid broadcasting”, which is an early data-centered protocol that greatly reduces startup latency and only requires a server bandwidth that is logarithmic in the length of the content instead of linear. A media object is partitioned into segments, where the segment size may vary. Each segment is transmitted repeatedly in a looping fashion at the same rate as the other segments, where a different channel may be used for each segment. Many other similar schemes have also been proposed to reduce the client startup latency or the maximum client temporary storage requirement for pyramid broadcasting, where the temporary storage requirement is the storage the client needs to save the data for the media object that has been downloaded at the client and not played out. If the data is saved at the client, then the storage needed is at least the size of the media object. See, e.g., C. Aggarwal, J. Wolf, and P. Yu, “A permutation-based pyramid broadcasting scheme for video-on-demand systems”, Proc. IEEE Int'l Conf. on Multimedia Systems, (Hiroshima, Japan, June 1996); K. Hua and S. Sheu, “Skyscraper broadcasting: A new broadcasting system for metropolitan video-on-demand systems”, Proc. ACM SIGCOMM, pp. 89–100 (Cannes, France, 1997); and L. Gao, J. Kurose, and D. Towsley, “Efficient schemes for broadcasting popular videos”, Proc. Inter. Workshop on Network and Operating System Support for Digital Audio and Video, (July 1998). A characteristic of all these schemes is that they require that data within each segment be downloaded in order. A client therefore would have to wait for the beginning of each segment to be transmitted before beginning to download or play out the content from that segment.
U.S. Pat. No. 6,018,359 issued to Kermode (hereinafter “Kermode”) describes a generalized scheme wherein a client can download multiple segments simultaneously. Kermode proposes downloading the segments starting from any point and reordering the data at the client, which allows the clients to download the segments asynchronously. The Kermode scheme and the other data-centered schemes with varying segment sizes described above, impose a restriction that each segment be downloaded at a rate that is greater than or equal to the play out rate of the content. Another restriction is that every segment is served at the same rate.
A second class of data-centered protocols fixes the size of each segment to be equal, but varies the rate that each segment is transmitted. See, e.g., L. Juhn and L. Tseng, “Harmonic broadcasting for video-on-demand service”, IEEE Trans. on Broadcasting, 43:268–271 (September 1997) (hereinafter “Juhn97”); L. Juhn and L. Tseng, “Adaptive fast data broadcasting scheme for video-on-demand service”, IEEE Trans. on Broadcasting, 44:182–185 (June 1998); J. -F Paris, S. W. Carter, and D. D. E. Long, “Efficient broadcasting protocols for video on demand”, International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS), vol. 6, pages 127–132 (July 1998); J. -F Paris, S. W. Carter, and D. D. E. Long, “A low bandwidth broadcasting protocol for video on demand”, Proc. International Conference on Computer Communications and Networks, vol. 7, pages 690–697 (October 1998). Junh97 proposed an early scheme of this type, referred to as “harmonic broadcasting”. Harmonic broadcasting and its variants require that the client be able to download a media object at a rate that is at least as large as the server bandwidth assigned to the media object, which grows logarithmically with the content length.
Another restriction of all the above media-on-demand schemes is that if any of the data is lost, then they either don't play back in full fidelity, or else they have to wait for a complete cycle of that segment before the missing data piece is re-sent. Either scenario is sub-optimal. As described in U.S. Pat. No. 6,307,487 (U.S. patent application Ser. No. 09/246,015, filed Feb. 5, 1999 and entitled “Information Additive Code Generator And Decoder For Communication Systems”) (hereinafter “Luby I”) and U.S. Pat. No. 6,320,520 (U.S. patent application Ser. No. 09/399,201, filed Sep. 17, 1999 and entitled “Information Additive Group Code Generator And Decoder For Communication Systems” (hereinafter “Luby II”), chain reaction coding is a useful method of recovering from missing data in many communications systems. Luby I and Luby II describe the application of chain reaction codes for content download, and not for an on-demand media streaming application. In some implementations of chain reaction coding, the probability of a decoder being able to decode a media object is low until the decoder has collected enough data, where enough data is approximately the size of the entire media object. Thus, it is unlikely that a media object can be decoded in parts when the encoding is applied to the entire media object as a whole.